package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * @author By ZengPeng
 */
public class 力扣_81_搜索旋转排序数组II {
    //测试
    public static void main(String[] args) {

   /*     System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{2,5,6,0,0,1,2},0));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{2,5,6,0,0,1,2},6));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{2,5,6,0,0,1,2},2));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{0,0,1,2,2,5,6},0));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{0,0,1,2,2,5,6},6));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{0,1,2,3,4,5,6},7));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{0,1,2,3,4,5,6},0));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{0,1,2,3,4,5,6},6));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{0,1,2,3,4,5,6},6));
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1},2));*/
        System.out.println(new 力扣_81_搜索旋转排序数组II().search(new int[]{2,0,0,1},1));
    }

    /**
    题目：已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
     在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，
     使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
     例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
     给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。
     如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
     你必须尽可能减少整个操作步骤。

     示例 1：
     输入：nums = [2,5,6,0,0,1,2], target = 0
     输出：true

     示例 2：
     输入：nums = [2,5,6,0,0,1,2], target = 3
     输出：false

    分析：【Good】
       1.分段二分查找，找到中间值，判断左边有序还是右边有序
         注意：这里nums[left] == nums[mid] && nums[mid] ==nums[right]时，分不清那边有序，left++即可，左移去掉一个值

    边界值 & 注意点：
       1.
     **/
    public boolean search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while (left<=right){
            int mid  = left+(right-left)/2;
            if(nums[mid] ==target) return true;
            if(nums[left] == nums[mid] && nums[mid] ==nums[right]){
                left++;continue;
            }
            //判断哪边有序
            if(nums[mid]<=nums[right]){//右边有序
                if(target>nums[mid] && target<=nums[right])//在右边
                    left = mid+1;
                else
                    right = mid-1;
            }else {//左边有序
                if(target>=nums[left] && target<nums[mid])//在左边
                    right=mid-1;
                else
                    left=mid+1;
            }
        }
        return  false;
    }
}
